Search results for "Greedy coloring"
showing 9 items of 9 documents
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
Grundy coloring for power graphs
2003
International audience
Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
2013
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
Arc crossing minimization in graphs with GRASP
2001
Graphs are commonly used to represent information in many fields of science and engineering. Automatic drawing tools generate comprehensible graphs from data, taking into account a variety of properties, enabling users to see important relationships in the data. The goal of limiting the number of arc crossings is a well-admitted criterion for a good drawing. In this paper, we present a Greedy Randomized Adaptive Search Procedure (GRASP) for the problem of minimizing arc crossings in graphs. Computational experiments with 200 graphs with up to 350 vertices are presented to assess the merit of the method. We show that simple heuristics are very fast but result in inferior solutions, while hig…
A fast heuristic for solving the D1EC coloring problem
2010
In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a sub optimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergen…
A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
2010
This work proposes an efficient method for solving the Distance-1 Edge Coloring problem (D1EC) for the assignment of orthogonal channels in wireless networks with changing topology. The coloring algorithm is performed by means of the simulated annealing method, a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme. Furthermore, a stateful implementation of the D1EC scheme is proposed, in which network coloring is executed upon topology changes. The stateful D1EC is also based on simulated annealing and reduces the algorithm’s convergence time by one order of magnitude in …
Stochastic Learning for SAT- Encoded Graph Coloring Problems
2010
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.
Chromatic sums for colorings avoiding monochromatic subgraphs
2015
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …